<?php
namespace app\common\tools;

/**
* 异常类工厂调用基类
*/
class PhpSort
{
    /**
     * 冒泡排序 之一山更比一山高
     */
    public static function bubbleSort(Array $data = [])
    {
        $len = count($data);
        for($key=0; $key<$len-1; $key++){
            for ($i=0; $i<$len-$key-1; $i++) {
                if($data[$i] > $data[$i+1]) {
                    [$data[$i], $data[$i+1]] = [$data[$i+1], $data[$i]];
                }
            }
        }
        
        return $data;
    }

    /**
     * 选择排序 之擒贼先擒王
     */
    public static function selectSort(Array $data = [])
    {
        $len = count($data);
        for($key=0; $key<$len-1; $key++){
            for ($i=$key+1; $i < $len; $i++) {
                if($data[$key] > $data[$i]) {
                    [$data[$key], $data[$i]] = [$data[$i], $data[$key]];
                }
            }
        }
        
        return $data;
    }

    /**
     * 插入排序
     */
    public static function insertSort(Array $data = [])
    {
        
    }

    /**
     * 希尔排序
     */
    public static function shellSort(Array $data = [])
    {
        
    }

    public static function quickSort(Array $data = [])
    {
        $start = self::timedate();
        $data = self::quickSortHandle($data, 0 , count($data)-1);
        $end = self::timedate();

        echo ($end-$start)."  快速排序 之移形换位\n";
        return $data;
    }

    public static function quickSortOne(Array $data = [])
    {
        $start = self::timedate();
        $data = self::quickSortReset($data);
        $end = self::timedate();
        echo ($end-$start)." 快速排序 之合二为一\n";
        return $data;
    }

    /**
     * 快速排序 之移形换位
     */
    protected static function quickSortHandle(Array &$data = [], $start, $end)
    {
        if ($start >= $end) {
            return;
        }
        
        $left = $start;
        $right = $end;
        $mid = $data[$left];
        while ($left < $right) {
            while ($left < $right && $data[$right] >= $mid) {
                $right--;
            }
            $data[$left] = $data[$right];
            while ($left < $right && $data[$left] < $mid) {
                $left++;
            }
            $data[$right] = $data[$left]; 
        }

        if ($left == $right) {
            $data[$left] = $mid;
        }
        
        self::quickSortHandle($data, $start, $left-1);
        self::quickSortHandle($data, $left+1, $end);
        return $data;    
    }

    /**
     * 快速排序 之合二为一
     */
    protected static function quickSortReset(Array $data = [])
    {
        $len = count($data);
        if ($len <= 1) {
            return $data;
        }
        $left = [];
        $right = [];
        $mid = $data[0];
        for ($i=1; $i < $len; $i++) { 
            if ($data[$i] <= $mid) {
                $left[] = $data[$i];
            } else {
                $right[] = $data[$i];
            }
        }

        $left = self::quickSortReset($left);
        $right = self::quickSortReset($right);
        
        return array_merge($left, [$mid],$right);
    }
    
    /**
     * 归并排序 之分而治之
     */
    public static function mergeSort(Array $data = [])
    {
        $len = count($data);
        if ($len <= 1) {
            return $data;
        }

        $mid = floor($len/2);
        $left = array_slice($data, 0, $mid);
        $left = self::mergeSort($left);
        $right = array_slice($data, $mid);
        $right = self::mergeSort($right);

        $res = [];
        $left_index = 0;
        $right_index = 0;
        while($left_index < count($left) && $right_index < count($right)) {
            if ($left[$left_index] < $right[$right_index]) {
                $res[] = $left[$left_index];
                $left_index++;
            } else {
                $res[] = $right[$right_index];
                $right_index++;
            }
        }

        $left = array_slice($left, $left_index);
        $right = array_slice($right, $right_index);
        return array_merge($res, $left, $right);
    }

    public static function timedate()
    {
        [$sec, $date] = explode(' ', microtime());
        printf("%s %s\n", date("Y-m-d H:i:s", $date), $sec);

        return $sec * 10000000;
    }
}